import java.util.Random;

public class Page {
	static final int PAGE_NUM = 4;
	static final int PAGE_REF = 10;
	static final int TOTAL_PAGE_REF = 100;
	static final boolean ENABLE_PRINT_TABLE = true;
	
	protected static int[] randomGen() {
		Random r = new Random();
		int[] refAry = new int[TOTAL_PAGE_REF];
		for (int i = 0; i < TOTAL_PAGE_REF; i++) {
			if (i == 0) {
				refAry[i] = r.nextInt(PAGE_REF);
			} else {
				int deltaI = 0;
				int prevRef = refAry[i-1];
				if (prevRef >= 0 && prevRef < 7) {
					if (r.nextDouble() <= 0.7){
						deltaI = r.nextInt(3) - 1;
						refAry[i] = Math.abs((prevRef + deltaI) % 9); 
					} else {
						deltaI = r.nextInt(PAGE_REF);
						refAry[i] = Math.abs((prevRef + deltaI) % 9); 
					}
				} else {
					deltaI = r.nextInt(8) + 2;
					refAry[i] = Math.abs((prevRef + deltaI) % 9);
				}
			}
		}
		return refAry;
	}
	
	/**
	 * Simulate the FIFO Page Replacement Algorithm
	 * @param refAry Array with 100 references 
	 * @return Hit ratio of FIFO
	 */
	protected static double FIFO(int[] refAry) {
		System.out.println("\nTime\tFrame1\tFrame2\tFrame3\tFrame4\tHit?\tPage_In\tEvicted");
		int hitCount = 0;
		int faultCount = 0;
		
		//To store the simulation results at each time slices
		int[] simTable = new int[PAGE_NUM];
		
		//Initialize all elements of the simulation table to -1
		for (int i = 0; i < PAGE_NUM; i++) {
			simTable[i] = -1;
		}
		for (int i = 0; i < TOTAL_PAGE_REF; i++) {
			int position = faultCount % PAGE_NUM;
			boolean isHit = checkHit(refAry[i], simTable);
			if (isHit) {
				hitCount++;
				int hitPos = 0;
				for (int j = 0; j < PAGE_NUM; j++) {
					if (simTable[j] == refAry[i]) {
						hitPos = j;
						break;
					}
				}
				printSimulation(i, simTable, isHit, refAry[i], simTable[hitPos]);
				continue;
			}
			int evicted = simTable[position];
			simTable[position] = refAry[i];
			printSimulation(i, simTable, isHit, refAry[i], evicted);
			faultCount++;
		}
		
		double hitRatio =  (double) hitCount / (double) TOTAL_PAGE_REF;
		return hitRatio;
	}
	
	/**
	 * Simulate Second Chance Page Replacement Algorithm
	 * @param refAry Array with 100 references 
	 * @return Hit ratio of Second Chance Page Replacement Algorithm
	 */
	protected static double SC(int[] refAry) {
		System.out.println("\nTime\tFrame1\tFrame2\tFrame3\tFrame4\tHit?\tPage_In\tEvicted");
		int hitCount = 0;
		int posCount = 0;
		
		//To store the simulation results at each time slices
		int[] simTable = new int[PAGE_NUM];
		
		//To determine if each page frame has a second chance
		boolean[] secondChance = new boolean[PAGE_NUM];
		
		for (int i = 0; i < PAGE_NUM; i++) {
			simTable[i] = -1;
			secondChance[i] = false;
		}
		
		for (int i = 0; i < TOTAL_PAGE_REF; i++) {
			boolean isHit = checkHit(refAry[i], simTable);
			int position = posCount % PAGE_NUM;
			if (isHit) {
				hitCount++;
				int hitPos = 0;
				for (int j = 0; j < PAGE_NUM; j++) {
					if (simTable[j] == refAry[i]) {
						hitPos = j;
						break;
					}
				}
				if (!secondChance[hitPos]) secondChance[hitPos] = true;
				printSimulation(i, simTable, isHit, refAry[i], simTable[hitPos]);
				continue;
			}
			for (int j = 0; j < PAGE_NUM + 1; j++) {
				int tempPos = (position + j) % PAGE_NUM;
				if (secondChance[tempPos]) {
					secondChance[tempPos] = false;
				} else {
					int evicted = simTable[tempPos];
					simTable[tempPos] = refAry[i];
					printSimulation(i, simTable, isHit, refAry[i], evicted);
					break;
				}
			}
			posCount++;
			
		}
		
		double hitRatio = (double) hitCount / (double) TOTAL_PAGE_REF;
		return hitRatio;
		
	}
	
	protected static double LRU(int[] refAry) {
		System.out.println("\nTime\tFrame1\tFrame2\tFrame3\tFrame4\tHit?\tPage_In\tEvicted");
		int hitCount = 0;
		int posCount = 0;
		
		//To store the simulation results at each time slices
		int[] simTable = new int[PAGE_NUM];
		
		//To store used record
		int[] usedTime = new int[PAGE_NUM];
		
		for (int i = 0; i < PAGE_NUM; i++) {
			simTable[i] = -1;
			usedTime[i] = -1;
		}
		
		for (int i = 0; i < TOTAL_PAGE_REF; i++) {
			boolean isHit = checkHit(refAry[i], simTable);
			if (isHit) {
				hitCount++;
				int hitPos = 0;
				for (int j = 0; j < PAGE_NUM; j++) {
					if (simTable[j] == refAry[i]) {
						hitPos = j;
						break;
					}
				}
				usedTime[hitPos] = i;
				printSimulation(i, simTable, isHit, refAry[i], simTable[hitPos]);
				continue;
			}
			int position = 0;
			for (int j = 0; j < PAGE_NUM; j++) {
				if (usedTime[position] > usedTime[j]) {
					position = j;
				}
			}
			int evicted = simTable[position];
			simTable[position] = refAry[i];
			usedTime[position] = i;
			printSimulation(i, simTable, isHit, refAry[i], evicted);
		}
		
		double hitRatio = (double) hitCount / (double) TOTAL_PAGE_REF;
		return hitRatio;
	}
	
	
	protected static double Random(int[] refAry) {
		System.out.println("\nTime\tFrame1\tFrame2\tFrame3\tFrame4\tHit?\tPage_In\tEvicted");
		int hitCount = 0;
		int posCount = 0;
		Random r = new Random();
		
		//To store the simulation results at each time slices
		int[] simTable = new int[PAGE_NUM];
		for (int i = 0; i < PAGE_NUM; i++) {
			simTable[i] = -1;
		}
		
		for (int i = 0; i < TOTAL_PAGE_REF; i++) {
			boolean isHit = checkHit(refAry[i], simTable);
			if (isHit) {
				hitCount++;
				int hitPos = 0;
				for (int j = 0; j < PAGE_NUM; j++) {
					if (simTable[j] == refAry[i]) {
						hitPos = j;
						break;
					}
				}
				printSimulation(i, simTable, isHit, refAry[i], simTable[hitPos]);
				continue;
			}
			int position = 0;
			int simTableCheck = 0;
			while (simTableCheck < PAGE_NUM) {
				if(simTable[simTableCheck] == -1) break;
				simTableCheck++;
			}
			if (simTableCheck < PAGE_NUM) position = simTableCheck;
			else position = r.nextInt(PAGE_NUM);
			int evicted = simTable[position];
			simTable[position] = refAry[i];
			printSimulation(i, simTable, isHit, refAry[i], evicted);
		}
		
		double hitRatio = (double) hitCount / (double) TOTAL_PAGE_REF;
		return hitRatio;
	}
	private static void printSimulation(int time, int[] simTable, boolean isHit, int curRef, int evicted) {
		if (!ENABLE_PRINT_TABLE) return;
		if (simTable.length == PAGE_NUM) {
			System.out.print(time+"\t");
			for (int i = 0; i < PAGE_NUM; i++) {
				System.out.print(simTable[i]+"\t");
			}
			if (isHit) {
				System.out.print("Hit\t");
			} else {
				System.out.print("Fault\t");
			}
			System.out.println(curRef + "\t" + evicted);
		} else {
			System.out.println("This is not the Simulation Table.");
		}
	}
	
	private static boolean checkHit(int ref, int[] simTable) {
		for (int i = 0; i < simTable.length; i++) {
			if (ref == simTable[i]) {
				return true;
			}
		}
		return false;
	}
	
	private static double getAverage(double[] ary) {
		double result = 0;
		for (int i = 0; i < ary.length; i++) {
			result += ary[i];
		}
		result = result / ary.length;
		return result;
	}
	
	public static void main(String[] args) {
		System.out.println("-1 Means Empty Page Frame");
		final int SIM_TIME = 5;
		
		double[] fifoAry = new double[5];
		double[] scAry = new double[5];
		double[] lruAry = new double[5];
		double[] rAry = new double[5];
		
		System.out.println("FIFO Simulation");
		for (int i = 0; i < SIM_TIME; i++) {
			int[] refAry = randomGen();
			fifoAry[i] = FIFO(refAry);
		}
		
		System.out.println("SC Simulation");
		for (int i = 0; i < SIM_TIME; i++) {
			int[] refAry = randomGen();
			scAry[i] = SC(refAry);
		}
		
		System.out.println("LRU Simulation");
		for (int i = 0; i < SIM_TIME; i++) {
			int[] refAry = randomGen();
			lruAry[i] = LRU(refAry);
		}
		
		System.out.println("Random Simulation");
		for (int i = 0; i < SIM_TIME; i++) {
			int[] refAry = randomGen();
			rAry[i] = Random(refAry);
		}
		
		double fifoAvg = getAverage(fifoAry);
		double scAvg = getAverage(scAry);
		double lruAvg = getAverage(lruAry);
		double rAvg = getAverage(rAry);
		
		System.out.println("\nFIFO Average Time is " + fifoAvg);
		System.out.println("SC Average Time is " + scAvg);
		System.out.println("LRU Average Time is " + lruAvg);
		System.out.println("Random Average Time is " + rAvg);
		System.out.println("-1 Means Empty Page Frame");
	}
}